{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# XGBoost简介\n",
    "XGBoost 的全称是 eXtreme Gradient Boosting，它是经过优化的**分布式梯度提升库**。\n",
    "\n",
    "特点\n",
    "- 高效：它是目前最快最好的开源 boosting tree 工具包，比常见的工具包快 10 倍以上。\n",
    "- 适用广泛：适用于大量问题。\n",
    "- 可移植：在工业界大规模数据方面，XGBoost 的分布式版本有广泛的可移植性，支持在 Kubernetes、Hadoop、SGE、MPI、 Dask 等各个分布式环境上运行，使得它可以很好地解决工业界大规模数据的问题。\n",
    "\n",
    "GBDT 是机器学习算法，XGBoost 是该算法的工程实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# XGBoost的原理\n",
    "> Q1：如何构造目标函数？\n",
    "\n",
    "> A1：损失函数（经验损失）+正则项（树的复杂度惩罚/结构损失）\n",
    "\n",
    "> Q2：直接构造的目标函数是离散的，难以优化，如何近似一个更易优化的目标函数？\n",
    "\n",
    "> A2：利用泰勒级数，将目标函数展开成一个多项式函数（最高次为2）的形式\n",
    "\n",
    "> Q3：如何把树的结构引入目标函数？\n",
    "\n",
    "> A3：将树进行参数化（用数学语言描述一颗树）\n",
    "\n",
    "> Q4：如何生成一棵树？（实际就是如何从根结点开始，选择一个最优划分，以及何时停止划分）\n",
    "\n",
    "> A4：基于贪心算法（Exact Greedy Algorithm），后面再引出一种基于贪心算法的优化方法（Approximate Algorithm）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 构造目标函数\n",
    "> XGBoost的训练过程是一种叠加式的训练，具体来说若已知$t-1$颗树，我们希望在第$t$次训练后得到第$t$颗树。通过这种方法我们最后可以训练出所有树，最后我们也就得到了最终的模型。\n",
    "\n",
    "> 我们的目标：构造并最小化一个最终模型的目标函数\n",
    "\n",
    "目标函数的定义如下$$Obj=\\sum_{i=1}^nl(y_i,\\hat{y}_i)+\\sum_{i=1}^t \\Omega(f_i)$$\n",
    "等式右边第二项表示正则化项，它表示将$t$颗树的复杂度进行求和。\n",
    "\n",
    "由于XGBoost是boosting族中的算法，所以遵从前向分步加法，以第$t$步的模型为例，模型对第$i$个样本$x_i$的预测值为：$$\\hat{y}_i^{(t)}=\\hat{y}_i^{(t-1)}+f_t(x_i)$$，$\\hat{y}_i^{(t-1)}$是第$t$步的模型给出的预测值，$f_t(x_i)$是待加入的新模型的预测值。这时，目标函数可以写为\n",
    "![](目标函数1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上式的变量的只有第$t$颗树$f_t(x)$，其他变量要么已知，要么可由已知量计算出。\n",
    "\n",
    "**注**：前面$t-1$颗树已知，因此$t-1$颗树的复杂度之和可由常量$constant$代替。即$$\\sum_{i=1}^t \\Omega(f_i)=\\Omega(f_t)+\\sum_{i=1}^{t-1} \\Omega(f_i)=\\Omega(f_t)+constant$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "**下面将通过泰勒公式，近似目标函数**\n",
    "\n",
    "$f(x)$在$x=x_0$的二阶泰勒展开为$$f(x)=f(x_0)+f'(x_0)(x-x_0)+\\frac{1}{2}f''(x_0)(x-x_0)^2$$\n",
    "因此，$f(x+\\Delta x)$在点$x$的二阶泰勒展开为 $$f(x+\\Delta x)=f(x)+f'(x)(\\Delta x)+\\frac{1}{2}f''(x)(\\Delta x)^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上式，可写出$f_t(x)$的损失函数$l(y_i,\\hat{y}_i^{(t-1)}+f_t(x_i))$的二阶泰勒展开式\n",
    "$$l(y_i,\\hat{y}_i^{(t-1)}+f_t(x_i))=\\\\ l(y_i,\\hat{y}_i^{(t-1)})+\\frac{\\partial l(y_i,\\hat{y}_i^{(t-1)})}{\\partial \\hat{y}_i^{(t-1)}}f(x_i)+\\frac{1}{2}\\frac{\\partial^2 l(y_i,\\hat{y}_i^{(t-1)})}{\\partial(\\hat{y}_i^{(t-1)})^2}f_t^2(x_i)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将上述的展开式代入第$t$步的目标函数，可得目标函数的近似值\n",
    "$$Obj^{(t)}≈\\sum_{i=1}^n \\left [ l(y_i,\\hat{y}_i^{(t-1)})+\\frac{\\partial l(y_i,\\hat{y}_i^{(t-1)})}{\\partial \\hat{y}_i^{(t-1)}}f(x_i)+\\frac{1}{2}\\frac{\\partial^2 l(y_i,\\hat{y}_i^{(t-1)})}{\\partial(\\hat{y}_i^{(t-1)})^2}f_t^2(x_i) \\right ]+\\Omega(f_t)+constant$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于$\\hat{y}^{(t-1)}$是已知的，因此$l(y_i,\\hat{y}_i^{(t-1)})$是个常数。在优化时，常数项不会产生影响，因此去除所有常数项后得到的目标函数为\n",
    "$$Obj^{(t)}≈\\sum_{i=1}^n \\left [ \\frac{\\partial l(y_i,\\hat{y}_i^{(t-1)})}{\\partial \\hat{y}_i^{(t-1)}}f(x_i)+\\frac{1}{2}\\frac{\\partial^2 l(y_i,\\hat{y}_i^{(t-1)})}{\\partial(\\hat{y}_i^{(t-1)})^2}f_t^2(x_i) \\right ]+\\Omega(f_t)$$\n",
    "\n",
    "**注**：为记法方便，以后令$g_i=\\frac{\\partial l(y_i,\\hat{y}_i^{(t-1)})}{\\partial \\hat{y}_i^{(t-1)}}$，$h_i=\\frac{\\partial^2 l(y_i,\\hat{y}_i^{(t-1)})}{\\partial(\\hat{y}_i^{(t-1)})^2}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以我们只需要求出每一步损失函数的一阶导和二阶导的值（由于前一步的$\\hat{y}^{(t-1)}$是已知的，所以这两个值就是常数），然后最优化目标函数，就可以得到第$t$步的$f_t(x)$，最后根据加法模型得到一个整体模型。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树的参数化（刻画一棵树）\n",
    "> XGBoost的一颗树$f_t(x)$\n",
    "\n",
    "> 输入：样本$x_i$\n",
    "\n",
    "> 输出：对应叶结点的权值 \n",
    "\n",
    "XGBoost的基学习器即支持决策树也支持线性模型，在这里介绍的是基于决策树的模型。**在XGBoost中我们定义一颗决策树，它包含两部分**：\n",
    "1. **叶子结点的权重向量**$\\omega$\n",
    "2. 实例(样本)到叶子结点的映射关系$q$(本质是**树的分支结构**)\n",
    "\n",
    "**因此，$f_t(x)=\\omega_{q(x)}$**\n",
    "![](XGBoost定义一棵树.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 定义树的复杂度\n",
    "> Q：如何刻画树的复杂度？\n",
    "\n",
    "> A：看两部分：叶节点数、叶结点权值向量\n",
    "\n",
    "树的复杂度主要考察两部分：叶子结点的数量$T$和叶子结点的权重$\\omega$。一般来说，叶子结点较少、叶子结点的权重不高的模型较为简单。\n",
    "\n",
    "树的复杂度定义成$$\\Omega(f)=\\gamma T+\\frac{1}{2}\\lambda \\sum_{j=1}^T \\omega_j^2$$\n",
    "![](XGBoost树的复杂度定义.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 叶子结点归组\n",
    "将属于第$j$个叶结点的所有样本划入到一个样本集合$I_j$中，$I_j=\\{ i|q(x_i)=j\\}$（理解：样本$x_i$经过树结构$q$映射到第$j$个叶节点）。此时XGBoost的目标函数可以改写为：\n",
    "\n",
    "![](叶子节点归组.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 上式中2-3行的变化的理解：第二行是遍历所有的样本后求每个样本的损失函数，但样本最终会落在叶子节点上，所以我们也可以遍历叶子节点，然后获取叶子节点上的样本集合，最后再求损失函数。\n",
    "- $\\omega_q(x_i)=\\omega_j$，即第$j$个叶结点的权值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为简化表达式，定义$G_j=\\sum_{i \\in I_j}g_i$，$H_j=\\sum_{i \\in I_j}h_i$，含义如下：\n",
    "- $G_j=\\sum_{i \\in I_j}g_i$：叶结点$j$所包含样本的一阶偏导数累加之和，是一个常量\n",
    "- $H_j=\\sum_{i \\in I_j}h_i$：叶结点$j$所包含样本的二阶偏导数累加之和，是一个常量\n",
    "\n",
    "将$G_j=\\sum_{i \\in I_j}g_i$和$H_j=\\sum_{i \\in I_j}h_i$带入XGBoost的目标函数，则**最终的目标函数**为：\n",
    "$$Obj^{(t)}=\\sum_{j=1}^T \\left [ G_j \\omega_j + \\frac{1}{2}(H_j+\\lambda)\\omega_j^2 \\right ] + \\gamma T$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 获得最好的树（目标函数的最小值）\n",
    "> 使用二次函数求最值的方法求XGBoost的目标函数的最值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$G_j$和$H_j$相对于第$j$棵树来说是可以计算出来的。那么，这个式子就是一个只包含一个变量叶子结点权重$\\omega_j$的一元二次函数，我们可以通过最值公式求出它的最值点。\n",
    "\n",
    "分析一下目标函数$Obj^{(t)}$，可以发现，**各个叶子结点的目标子式是相互独立的**，也就是说，当每个叶子结点的子式都达到最值点时，整个目标函数才达到最值点。\n",
    "\n",
    "因此，对于每一个叶结点，$$G_j \\omega_j + \\frac{1}{2}(H_j+\\lambda)\\omega_j^2$$对$\\omega_j$求一阶导数，令其为0，可得该叶结点的权值$$\\omega_j^*=-\\frac{G_j}{H_j+\\lambda}$$，可化简目标函数为$$Obj=-\\frac{1}{2}\\sum_{j=1}^T \\frac{G_j^2}{H_j+\\lambda}+\\gamma T$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面是一个实例：\n",
    "\n",
    "![](XGBoost目标函数的实例.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最优切分点划分算法\n",
    "> Q：在实际训练过程中，当建立第$t$棵树时，一个非常关键的问题是**如何找到叶子节点的最优切分点（确定一颗树的分支结构）**？\n",
    "\n",
    "> A：贪心算法或近似算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 贪心算法\n",
    "从树的深度为0开始\n",
    "1. 对每个叶节点枚举所有的可用特征\n",
    "2. 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该**特征的分裂收益**\n",
    "3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集\n",
    "4. 回到第1步，递归执行直到满足特定条件为止\n",
    "\n",
    "> Q：如何定义每个特征的分裂收益？\n",
    "\n",
    "> A；分裂前后目标函数的差\n",
    "\n",
    "![](分裂前后的目标函数之差.png)\n",
    "- 可以看到这里的贪心法和CART中生成树的算法思想很想，区别在于CART中特征的分裂收益由基尼值或均方误差定义。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Q；对于每次分裂，我们都需要枚举所有特征可能的分割方案，如何高效地枚举所有的分割呢？\n",
    "\n",
    "> A：对于所有的分裂点$a$，只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和$G_L$、$G_R$  \n",
    "\n",
    "**实例**\n",
    "\n",
    "假设我们要枚举某个特征所有满足$x<a$这个条件的样本，对于某个特定的分割点$a$我们要计算$a$左边和$a$右边样本的导数和\n",
    "\n",
    "![](左右导数和.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 近似算法\n",
    "> 贪心算法可以得到最优解，但当数据量太大时则无法读入内存进行计算，近似算法主要针对贪心算法这一缺点给出了近似最优解。\n",
    "\n",
    "> 近似算法的优化策略：对于每个特征，只考察分位点（可以减少计算复杂度）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基本思想\n",
    "1. 根据特征分布的分位数提出**候选划分点**\n",
    "2. 将连续型特征映射到由这些**候选点划分的区间（桶）**中\n",
    "3. 聚合统计信息找到所有区间的最佳分裂点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "提出候选切分点时有两种策略\n",
    "1. Global：学习每棵树前就提出候选切分点，并在每次分裂时都采用这种分割；\n",
    "2. Local：每次分裂前将重新提出候选切分点。直观上来看，Local策略需要更多的计算步骤，而Global策略因为节点已有划分所以需要更多的候选点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下图给出不同种分裂策略的AUC变化曲线，横坐标为迭代次数，纵坐标为测试集AUC，`eps`为近似算法的精度，其倒数为桶的数量。\n",
    "![](测试AUC的收敛性比较.png)\n",
    "- Global策略在候选点较多时可以具有和Local策略相似的精度。\n",
    "- `eps`取值合适时，分位数近似策略可以获得与贪心算法相同的精度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "近似算法的描述如下：\n",
    "\n",
    "![](Approximate_Algorithm.jpg)\n",
    "- 第一个for循环：根据特征$k$的分布找到切分候选点集合$S_k$。这样做的好处是无需遍历所有可能的切分点，从而节省了时间。此外XGBoost还提供了Global和local两种选择候选点的策略。\n",
    "- 第二个for循环：将每个特征值映射到候选点划分出的区间（桶）中，即$s_{k,v}≥X_{jk}>s_{k,v-1}$。对每个桶中的样本的$G$和$H$值进行累加，然后在这些累加的统计量上寻找最佳分裂点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "看一个实例：\n",
    "![](近似算法举例：三分位数.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 加权分位数缩略图\n",
    "> 实际上，XGBoost不是简单地按照样本个数进行分位，而是以二阶导数值$h_i$作为样本的权重进行划分。为了处理带权重的候选切分点的选取，作者提出了`Weighted Quantile Sketch`算法。这里不表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 稀疏感知算法（Sparsity-aware Split Finding）\n",
    "> Q1：实际工程中一般会出现输入值稀疏的情况。比如数据的缺失、one-hot编码都会造成输入数据稀疏。XGBoost中如何处理稀疏值？\n",
    "\n",
    "> A1：XGBoost在构建树的结点时只遍历非缺失值。当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。\n",
    "\n",
    "> Q2：如何学到缺省方向？\n",
    "\n",
    "> A2：XGBoost提出了`Sparsity-aware Split Finding`\n",
    "算法。其主要思想是分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](缺省方向.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Sparsity-aware Split Finding`算法的描述\n",
    "![](Sparsity-aware_Split_Finding.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 工程实现\n",
    "> **注**：这部分内容还没深入理解\n",
    "## 列块并行学习\n",
    "> Q：在寻找最佳分裂点时，无论是贪心算法还是近似算法，都需要对特征值进行排序，那么在大规模数据集中如何高效的完成这一步？\n",
    "\n",
    "> A： XGBoost 在训练之前会根据特征对数据进行排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式（Compressed Sparse Columns Format，CSC）进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分块存储后多个特征之间互不干涉，可以使用多线程同时对不同的特征进行切分点查找，即特征的并行化处理。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 缓存访问\n",
    "> Q：通过特征值持有的索引（样本索引）访问样本获取一阶、二阶导数时，这个访问操作访问的内存空间并不连续，这样可能造成cpu缓存命中率低，影响算法效率。\n",
    "\n",
    "> A：XGBoost 提出了缓存访问算法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就实现了非连续空间到连续空间的转换，提高了算法效率。此外适当调整块大小，也可以有助于缓存优化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## “核外”块计算\n",
    "> Q1：当数据量非常大时，我们不能把所有的数据都加载到内存中。那么就必须将一部分需要加载进内存的数据先存放在硬盘中，当需要时再加载进内存。这样操作具有很明显的瓶颈，即硬盘的IO操作速度远远低于内存的处理速度，肯定会存在大量**等待硬盘IO操作**的情况。\n",
    "\n",
    "> A1：XGBoost提出“核外”计算的方法（将内存处理数据与从硬盘读取数据进行并行）：将数据集分成多个块存放在硬盘中，使用一个独立的线程专门从硬盘读取数据，加载到内存中，这样算法在内存中处理数据就可以和从硬盘读取数据同时进行。\n",
    "\n",
    "> Q2：如何降低硬盘读写开销？\n",
    "\n",
    "> A2：块压缩（Block Compression）或块分区（Block Sharding ）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# XGBoost的优缺点\n",
    "## 优点\n",
    "- 精度更高： GBDT只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。\n",
    "- 灵活性更强：\n",
    "    - GBDT以CART作为基分类器，XGBoost不仅支持CART还支持线性分类器。\n",
    "    - XGBoost支持自定义损失函数，只需损失函数具有一、二阶导数。\n",
    "- 支持正则化项：XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。  # GBDT没有显式的正则化项\n",
    "- 支持列抽样： XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。 #  GBDT没有\n",
    "- 支持Shrinkage（缩减）：相当于学习率。削弱每棵树的影响，让后面有更大的学习空间。  # GBDT有\n",
    "- 自动处理缺失值：对于含缺失值的样本，XGBoost的稀疏感知算法可以自己学习出该样本的分裂方向。  # GBDT没有\n",
    "- 支持并行：XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第$t$次迭代的代价函数里包含了前面$t-1$次迭代的预测值）。XGBoost的并行是在特征粒度上的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 缺点\n",
    "- 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集（要计算样本的一、二阶导数）。\n",
    "- 预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# XGBoost类库使用小结\n",
    "> XGBoost支持多种语言。它的基学习器即支持决策树也支持线性模型，本节只探讨使用默认决策树弱学习器的XGBoost。\n",
    "\n",
    "XGBoost支持2种Python风格的API\n",
    "1. 原生Python API\n",
    "2. sklearn风格的API。根据参数风格，又可分为两种：使用原生参数的sklearn风格API；使用sklearn风格参数的sklearn风格API。\n",
    "\n",
    "两者的实现基本一样，区别主要在于参数命名上，以及数据集的初始化上面。下面主要介绍使用sklearn风格参数的sklearn风格API。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 安装XGBoost\n",
    "> 官方文档提供了XGBoost的Python包[安装教程](https://xgboost.readthedocs.io/en/latest/build.html)。\n",
    "\n",
    "> 安装较新版Anaconda时附带了XGBoost，因此无需手动安装了，"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 使用sklearn风格接口，使用sklearn风格参数\n",
    "对于sklearn风格的接口，主要有2个类可以使用，一个是分类用的`XGBClassifier`，另一个是回归用的`XGBRegressor`。下面是一个demo："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "import xgboost as xgb\n",
    "\n",
    "# 建立模型\n",
    "sklearn_model_new = xgb.XGBClassifier(max_depth=5, learning_rate= 0.5, verbosity=1, objective='binary:logistic', random_state=1)\n",
    "# 预测\n",
    "sklearn_model_new.fit(X_train, y_train, \n",
    "                      early_stopping_rounds=10, eval_metric=\"error\", eval_set=[(X_test, y_test)])\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## XGBoost类库参数\n",
    "XGBoost的类库参数主要包括boosting框架参数，弱学习器参数以及其他参数。\n",
    "\n",
    "### XGBoost框架参数\n",
    "最重要的3个XGBoost框架参数: booster，n_estimators和objectve\n",
    "1. booster：代表XGBoost使用的基学习器类型，默认是`gbtree`, 也就是CART决策树。还可以是线性弱学习器gblinear以及DART。\n",
    "2. n_estimators：代表要学习的基学习器个数/迭代次数。该值太小容易欠拟合，太大模型会太复杂。\n",
    "3. objectve：str，用于指定学习任务以及对应的损失函数。\n",
    "    - 回归问题：objective一般使用`'reg:squarederror' `，即MSE均方误差\n",
    "    - 二分类问题：一般使用`'binary:logistic'`\n",
    "    - 多分类问题：一般使用`'multi:softmax'`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### XGBoost基学习器参数 \n",
    "这里只介绍使用决策树为基学习器时需要设置的参数。\n",
    "1. max_depth：树的深度。如果模型样本量多，特征也多的情况下，需要限制这个最大深度。\n",
    "2. min_child_weight：最小的子节点权重阈值。如果某个树节点的权重小于这个阈值，则不会再分裂子树，即这个树节点就是叶子节点。这里树节点的权重使用的是该节点所有样本的二阶导数的和。\n",
    "3. gamma：XGBoost的决策树分裂所带来的损失减小阈值。即树的分裂后最大收益大于这个值时才会分裂，否则停止分裂。\n",
    "4. subsample：子采样参数，介于$(0,1]$之间。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。可以先取1，如果发现过拟合后可以网格搜索调参找一个相对小一些的值。\n",
    "5. colsample_bytree/colsample_bylevel/colsample_bynode：三个参数都是用于特征采样的，默认都是不做采样，即使用所有的特征建立决策树。例如样本一共有64个特征，则假设colsample_bytree，colsample_bylevel和colsample_bynode都是0.5，则某一个树节点分裂时会随机采样8个特征来尝试分裂子树。\n",
    "6. reg_alpha/reg_lambda：原理部分介绍到正则化项由L1正则化和L2正则化两部分构成$$\\Omega(f)=\\gamma T+\\frac{1}{2}\\lambda \\sum_{j=1}^T \\omega_j^2$$reg_alpha和reg_lambda分别表示的就是$\\gamma$和$\\lambda$\n",
    "\n",
    "实际调参中，一般先调max_depth，min_child_weight和gamma。如果发现有过拟合的情况下，再尝试调后面几个参数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### XGBoost其他参数\n",
    "1. learning_rate：控制每个弱学习器的权重缩减系数，也叫做学习率/步长。较小的learning_rate意味着需要更多的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。\n",
    "2. n_jobs：XGBoost算法的并发线程数。\n",
    "3. scale_pos_weight：float，平衡正例和负例的权重。用于类别不平衡时。\n",
    "4. importance_type：string, 默认是`\"gain\"`。查询各个特征的重要性程度，可以选择“gain”, “weight”, “cover”, “total_gain” 或者 “total_cover”。“weight”通过特征被选中作为分裂特征的计数来计算重要性，“gain”和“total_gain”则通过分别计算特征被选中做分裂特征时带来的平均增益和总增益来计算重要性。“cover”和 “total_cover”通过计算特征被选中做分裂时的平均样本覆盖度和总体样本覆盖度来来计算重要性。\n",
    "5. verbosity：训练过程中打印的日志等级，0 (silent), 1 (warning), 2 (info), 3 (debug)。默认是1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "verbosity## 实例\n",
    "创建数据集\n",
    "- 样本数：10000\n",
    "- 特征数：20\n",
    "- 输出类别：2个\n",
    "- 冗余特征：无\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "D:\\Anaconda\\lib\\site-packages\\sklearn\\utils\\deprecation.py:143: FutureWarning: The sklearn.datasets.samples_generator module is  deprecated in version 0.22 and will be removed in version 0.24. The corresponding classes / functions should instead be imported from sklearn.datasets. Anything that cannot be imported from sklearn.datasets is now part of the private API.\n",
      "  warnings.warn(message, FutureWarning)\n"
     ]
    }
   ],
   "source": [
    "from sklearn.datasets.samples_generator import make_classification\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "X, y = make_classification(n_samples=10000, n_features=20, n_redundant=0, n_clusters_per_class=1, n_classes=2, flip_y=0.1)\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "建立/训练模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "import xgboost as xgb\n",
    "xgb_clf = xgb.XGBClassifier(n_estimators=15, objective='binary:logistic',\n",
    "                           max_depth=4, verbosity=1, random_state=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0]\tvalidation_0-error:0.16080\n",
      "Will train until validation_0-error hasn't improved in 10 rounds.\n",
      "[1]\tvalidation_0-error:0.15840\n",
      "[2]\tvalidation_0-error:0.15680\n",
      "[3]\tvalidation_0-error:0.15840\n",
      "[4]\tvalidation_0-error:0.15840\n",
      "[5]\tvalidation_0-error:0.15920\n",
      "[6]\tvalidation_0-error:0.15920\n",
      "[7]\tvalidation_0-error:0.16120\n",
      "[8]\tvalidation_0-error:0.16080\n",
      "[9]\tvalidation_0-error:0.16000\n",
      "[10]\tvalidation_0-error:0.16040\n",
      "[11]\tvalidation_0-error:0.16080\n",
      "[12]\tvalidation_0-error:0.16160\n",
      "Stopping. Best iteration:\n",
      "[2]\tvalidation_0-error:0.15680\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "XGBClassifier(base_score=0.5, booster=None, colsample_bylevel=1,\n",
       "              colsample_bynode=1, colsample_bytree=1, gamma=0, gpu_id=-1,\n",
       "              importance_type='gain', interaction_constraints=None,\n",
       "              learning_rate=0.300000012, max_delta_step=0, max_depth=4,\n",
       "              min_child_weight=1, missing=nan, monotone_constraints=None,\n",
       "              n_estimators=15, n_jobs=0, num_parallel_tree=1, random_state=1,\n",
       "              reg_alpha=0, reg_lambda=1, scale_pos_weight=1, subsample=1,\n",
       "              tree_method=None, validate_parameters=False, verbosity=1)"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xgb_clf.fit(X_train, y_train, early_stopping_rounds=10, eval_metric=\"error\", eval_set=[(X_test, y_test)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8404"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xgb_clf.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reference\n",
    "1. Chen T, Guestrin C. Xgboost: A scalable tree boosting system[C]//Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. 2016: 785-794.\n",
    "2. [深入理解XGBoost](https://mp.weixin.qq.com/s?__biz=MzI5NDMzMjY1MA==&mid=2247485408&idx=1&sn=e9817887d4c3c2bbf4642c6f8389a8d8&chksm=ec653665db12bf73978040e7ec49a77341d44d4c443186a54caaa2fcc985608ab2e7890a55f1&scene=158#rd)\n",
    "3. [贪心学院xgboost](https://www.bilibili.com/video/BV1mZ4y1j7UJ?from=search&seid=18385136194902233696)\n",
    "3. [XGBoost类库使用小结](https://www.cnblogs.com/pinard/p/11114748.html)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
